//公交线路顺序结构实现

#include <iostream>
#include <string>
using namespace std;

// 站点结构体：封装站点名称和与上一站的距离
struct Station {
    string name;     // 站点名称
    double distance; // 与上一站的距离（单位：km）
};
// 公交线路类：基于顺序表实现站点管理
const int MAX_STATIONS = 100; // 最大站点容量
class BusLine {
private:
    Station stations[MAX_STATIONS]; // 顺序表存储站点
    int length;                     // 当前站点数量
public:
    // 构造函数：初始化站点数量为0
    BusLine() : length(0) {}

    // 1. 增加站点（在末尾添加）
    bool addStation(const string& name, double distance) {
        if (length >= MAX_STATIONS) {
            return false; // 容量已满
        }
        stations[length].name = name;
        stations[length].distance = distance;
        length++;
        return true;
    }
    // 2. 删除站点（按索引）
    bool deleteStation(int index) {
        if (index < 0 || index >= length) {
            return false; // 索引无效
        }
        for (int i = index; i < length - 1; i++) {
            stations[i] = stations[i + 1];
        }
        length--;
        return true;
    }
    // 3. 修改站点信息（按索引）
    bool modifyStation(int index, const string& newName, double newDistance) {
        if (index < 0 || index >= length) {
            return false; // 索引无效
        }
        stations[index].name = newName;
        stations[index].distance = newDistance;
        return true;
    }
    // 4. 查询站点（按索引）
    Station* queryStationByIndex(int index) {
        if (index < 0 || index >= length) {
            return nullptr; // 索引无效
        }
        return &stations[index];
    }
    // 5. 查询站点（按名称）
    Station* queryStationByName(const string& name) {
        for (int i = 0; i < length; i++) {
            if (stations[i].name == name) {
                return &stations[i];
            }
        }
        return nullptr; // 未找到
    }
    // 显示所有站点信息
    void displayAllStations() {
        if (length == 0) {
            cout << "公交线路暂无站点！" << endl;
            return;
        }
        cout << "公交线路站点信息：" << endl;
        for (int i = 0; i < length; i++) {
            cout << "站点" << i + 1 << "：" << stations[i].name
                 << "，与上一站距离：" << stations[i].distance << "km" << endl;
        }
    }
};

// 主函数：测试公交线路功能
int main() {
    BusLine line17; // 模拟17路公交线路
    // 添加站点
    line17.addStation("公交总站", 0.0);
    line17.addStation("中心广场", 1.2);
    line17.addStation("科技园区", 2.5);
    // 显示所有站点
    line17.displayAllStations();
    // 修改站点
    line17.modifyStation(1, "新中心广场", 1.3);
    // 查询站点
    Station* sta = line17.queryStationByName("科技园区");
    if (sta) {
        cout << "查询到站点：" << sta->name << "，与上一站距离：" << sta->distance << "km" << endl;
    }
    // 删除站点
    line17.deleteStation(0);
    line17.displayAllStations();
    return 0;
}







//公交线路链式结构实现
#include <iostream>
#include <string>
using namespace std;

// 存储单个站点信息
typedef struct Node
{
    string name;          // 站点名称
    int distance;         // 与上一站的距离(单位:米)
    struct Node* next;    // 指向下一个站点的指针
} Node;

typedef struct
{
    string line_name;     // 线路名称(如"17路")
    Node* head;           // 指向首站点的指针
    int length;           // 站点总数
} List;

// 函数声明
void Initialization(List*& L, const string& line_name);          // 初始化线路
void Destroy(List*& L);                               // 销毁线路
void Insert(List*& L, int i, const string& a, int b);  // 插入站点
int Count(List* L);                                  // 获取站点数量
bool getinformation(List* L, int i, string& a, int& b);          // 获取站点信息
bool Delete(List*& L, int i, string& a, int& b);      // 删除站点
void Modify(List* L, int i, const string& new_name, int new_distance);  // 修改站点

// 初始化线路
void Initialization(List*& L, const string& line_name)
{
    L = new List;
    L->line_name = line_name;
    L->head = NULL;
    L->length = 0;
    cout << "线路 \"" << line_name << "\" 初始化成功!" << endl;
}

// 销毁线路
void Destroy(List*& L) {
    if (L == NULL) return;
    
    Node* current = L->head;
    while (current != NULL) {
        Node* next = current->next;
        delete current;
        current = next;
    }
    
    cout << "线路 \"" << L->line_name << "\" 销毁成功成功!" << endl;
    delete L;
    L = NULL;
}

// 插入站点
void Insert(List*& L, int i, const string& a, int b) {
    if (i < 1 || i > L->length + 1) {
        cout << "插入位置无效!" << endl;
        return;
    }

    Node* newNode = new Node;
    newNode->name = a;
    newNode->distance = b;
    newNode->next = NULL;

    // 插入到表头
    if (i == 1) {
        newNode->next = L->head;
        L->head = newNode;
    } else {
        // 找到前驱节点
        Node* prev = L->head;
        for (int j = 1; j < i - 1; j++) {
            prev = prev->next;
        }
        
        // 调整距离
        if (prev->next != NULL) {
            prev->next->distance -= b;
        }
        
        // 插入新节点
        newNode->next = prev->next;
        prev->next = newNode;
    }

    L->length++;
    cout << "站点 \"" << a << "\" 插入成功!" << endl;
}

// 获取站点数量
int Count(List* L)
{
    return L->length;
}

// 获取站点信息
bool getinformation(List* L, int i, string& a, int& b)
{
    if (i < 1 || i > L->length)
    {
        cout << "位置无效!" << endl;
        return false;
    }
    Node* p = L->head;
    for (int j = 1; j <= i - 1; j++)
    {
        p = p->next;
    }
    a = p->name;
    b = p->distance;
    return true;
}

// 删除站点
bool Delete(List*& L, int i, string& a, int& b) {
    if (i < 1 || i > L->length) {
        cout << "删除位置无效!" << endl;
        return false;
    }

    Node* nodeToDelete = NULL;

    // 删除表头
    if (i == 1) {
        nodeToDelete = L->head;
        L->head = nodeToDelete->next;
        
        // 如果不是最后一个节点，重置距离
        if (L->head != NULL) {
            L->head->distance = 0;
        }
    } else {
        // 找到前驱节点
        Node* prev = L->head;
        for (int j = 1; j < i - 1; j++) {
            prev = prev->next;
        }
        
        nodeToDelete = prev->next;
        
        // 调整下一个节点的距离
        if (nodeToDelete->next != NULL) {
            nodeToDelete->next->distance += nodeToDelete->distance;
        }
        
        // 删除节点
        prev->next = nodeToDelete->next;
    }

    // 保存删除节点的信息
    a = nodeToDelete->name;
    b = nodeToDelete->distance;
    
    // 释放内存
    delete nodeToDelete;
    L->length--;
    
    return true;
}
// 修改站点
void Modify(List* L, int i, const string& new_name, int new_distance)
{
    if (i < 1 || i > L->length)
    {
        cout << "修改位置无效!" << endl;
        return;
    }
    
    Node* p = L->head;
    for (int j = 1; j <= i - 1; j++)
    {
        p = p->next;
    }
    
    string old_name = p->name;
    int old_distance = p->distance;
    
    p->name = new_name;
    
    // 如果不是第一个站点，需要需要调整距离
    if (i > 1 && p->next != NULL)
    {
        int distance_change = new_distance - old_distance;
        p->distance = new_distance;
        
        // 调整下一站的距离
        Node* next_node = p->next;
        next_node->distance -= distance_change;
    }
    else
    {
        p->distance = new_distance;
    }
    
    cout << "站点 \"" << old_name << "\" 修改成功!" << endl;
}

// 测试函数
void Test()
{
    List* bus_line = NULL;
    string station_name;
    int distance;
    
    // 1. 初始化线路
    Initialization(bus_line, "17路");
    
    // 2. 添加站点
    Insert(bus_line, 1, "三元湖", 0);
    Insert(bus_line, 2, "体育场", 1500);
    Insert(bus_line, 3, "七餐", 1000);
    Insert(bus_line, 4, "钟楼", 800);
    cout << endl;
    
    // 3. 插入站点
    Insert(bus_line, 3, "六餐", 500);
    cout << endl;
    
    // 4.删除站点 
    if (Delete(bus_line, 3, station_name, distance))
    {
        cout << "删除的站点: " << station_name << endl;
    }
    cout << endl;
    
    // 5. 修改站点
    Modify(bus_line, 2, "东大活", 1600);
    cout << endl;
    // 6. 查找站点 
    if (getinformation(bus_line, 2, station_name, distance))
    {
        cout << "位置2的站点: " << station_name << ", 距离: " << distance << "米" << endl;
    }
    cout << endl;
    // 7. 销毁线路
    Destroy(bus_line);
    
    cout << "=== 程序结束 ===" << endl;
}

// 主函数
int main()
{
    Test();
    return 0;
}













//以下是换乘提高部分
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

// 公交线路类：新增getStations()接口，避免访问私有成员
class BusLine {
private:
    string lineName;          // 线路名称
    vector<string> stations;  // 站点列表

public:
    // 构造函数
    BusLine(string name, vector<string> stas) : lineName(name), stations(stas) {}
    
    // 获取线路名称
    string getLineName() const { return lineName; }
    
    // 获取站点列表（解决private访问问题）
    const vector<string>& getStations() const { return stations; }
    
    // 检查站点是否在线路上
    bool hasStation(const string& station) const {
        return find(stations.begin(), stations.end(), station) != stations.end();
    }
    
    // 获取站点在线路上的索引：替换auto为具体迭代器类型
    int getStationIndex(const string& station) const {
        vector<string>::const_iterator it = find(stations.begin(), stations.end(), station);
        if (it != stations.end()) {
            return it - stations.begin();
        }
        return -1;
    }
    
    // 获取下一个站点：修复signed/unsigned比较（强制转换size_t为int）
    string getNextStation(const string& current) const {
        int idx = getStationIndex(current);
        int stationsSize = static_cast<int>(stations.size()); // 转换为int
        if (idx != -1 && idx < stationsSize - 1) {
            return stations[idx + 1];
        }
        return "";
    }
    
    // 检查是否可以从起点直达终点
    bool canReachDirectly(const string& start, const string& end) const {
        int startIdx = getStationIndex(start);
        int endIdx = getStationIndex(end);
        return (startIdx != -1 && endIdx != -1 && startIdx < endIdx);
    }
};

// 查找两条线路的共同站点：用getStations()访问站点，替换range-based for
vector<string> findCommonStations(const BusLine& line1, const BusLine& line2) {
    vector<string> common;
    // 替换auto和range-based for为C++98迭代器循环
    vector<string>::const_iterator it1 = line1.getStations().begin();
    vector<string>::const_iterator it1End = line1.getStations().end();
    for (; it1 != it1End; ++it1) {
        if (line2.hasStation(*it1)) {
            common.push_back(*it1);
        }
    }
    return common;
}

// 生成换乘建议：替换nullptr为NULL，修复循环
void generateTransferAdvice(const BusLine& line1, const BusLine& line2, 
                           const string& start, const string& end) {
    // 检查起点和终点是否存在
    if (!line1.hasStation(start) && !line2.hasStation(start)) {
        cout << "起点站 " << start << " 不在任何一条线路上！" << endl;
        return;
    }
    
    if (!line1.hasStation(end) && !line2.hasStation(end)) {
        cout << "终点站 " << end << " 不在任何一条线路上！" << endl;
        return;
    }
    
    // 检查是否可以直达
    if (line1.canReachDirectly(start, end)) {
        cout << "无需换乘！乘坐" << line1.getLineName() << "路车，";
        cout << "从" << start << "出发，向" << line1.getNextStation(start) << "方向，";
        cout << "直达" << end << endl;
        return;
    }
    
    if (line2.canReachDirectly(start, end)) {
        cout << "无需换乘！乘坐" << line2.getLineName() << "路车，";
        cout << "从" << start << "出发，向" << line2.getNextStation(start) << "方向，";
        cout << "直达" << end << endl;
        return;
    }
    
    // 查找共同站点（换乘点）
    vector<string> commonStations = findCommonStations(line1, line2);
    if (commonStations.empty()) {
        cout << "两条线路没有共同站点，无法换乘！" << endl;
        return;
    }
    
    // 确定合适的换乘方案：替换nullptr为NULL
    BusLine* startLine = NULL;
    BusLine* endLine = NULL;
    
    if (line1.hasStation(start)) {
        startLine = const_cast<BusLine*>(&line1);
        endLine = const_cast<BusLine*>(&line2);
    } else if (line2.hasStation(start)) {
        startLine = const_cast<BusLine*>(&line2);
        endLine = const_cast<BusLine*>(&line1);
    }
    
    // 找到合适的换乘站：替换range-based for为迭代器循环
    string transferStation;
    vector<string>::const_iterator it = commonStations.begin();
    vector<string>::const_iterator itEnd = commonStations.end();
    for (; it != itEnd; ++it) {
        if (startLine->canReachDirectly(start, *it) && endLine->canReachDirectly(*it, end)) {
            transferStation = *it;
            break;
        }
    }
    
    if (transferStation.empty()) {
        cout << "没有合适的换乘方案！" << endl;
        return;
    }
    
    // 输出换乘建议
    cout << "换乘建议：" << endl;
    cout << "1. 乘坐" << startLine->getLineName() << "路车，从" << start << "出发，";
    cout << "向" << startLine->getNextStation(start) << "方向，前往换乘站" << transferStation << endl;
    cout << "2. 在" << transferStation << "换乘" << endLine->getLineName() << "路车，";
    cout << "向" << endLine->getNextStation(transferStation) << "方向，前往终点站" << end << endl;
}

int main() {
    // 初始化vector：替换C++11列表初始化，用push_back（C++98兼容）
    vector<string> line1Stations;
    line1Stations.push_back("A站");
    line1Stations.push_back("B站");
    line1Stations.push_back("C站");
    line1Stations.push_back("D站");
    line1Stations.push_back("E站");
    line1Stations.push_back("F站");
    BusLine line1("1", line1Stations);
    
    vector<string> line2Stations;
    line2Stations.push_back("X站");
    line2Stations.push_back("Y站");
    line2Stations.push_back("C站");
    line2Stations.push_back("Z站");
    line2Stations.push_back("F站");
    line2Stations.push_back("G站");
    BusLine line2("2", line2Stations);
    
    cout << "欢迎使用公交线路查询系统" << endl;
    cout << "1路车线路：";
    // 替换range-based for为迭代器循环
    vector<string>::const_iterator it1 = line1.getStations().begin();
    vector<string>::const_iterator it1End = line1.getStations().end();
    for (; it1 != it1End; ++it1) {
        cout << *it1 << " -> ";
    }
    cout << "终点" << endl;
    
    cout << "2路车线路：";
    vector<string>::const_iterator it2 = line2.getStations().begin();
    vector<string>::const_iterator it2End = line2.getStations().end();
    for (; it2 != it2End; ++it2) {
        cout << *it2 << " -> ";
    }
    cout << "终点" << endl;
    
    string start, end;
    cout << "请输入起点站：";
    cin >> start;
    cout << "请输入终点站：";
    cin >> end;
    
    generateTransferAdvice(line1, line2, start, end);
    
    return 0;
}





#include <iostream>
#include <stack>
#include <iomanip>
using namespace std;

// 迷宫大小:10×10
const int hang = 10;
const int lie = 10;
// 迷宫数组：1-不可走的墙壁，0-可走的路径，2-已走过的路径，3-终点
int migong[hang][lie] = {
    {1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
    {1, 0, 1, 1, 0, 0, 0, 1, 1, 1},
    {1, 0, 0, 0, 0, 1, 0, 0, 0, 1},
    {1, 0, 0, 1, 1, 1, 1, 0, 1, 1},
    {1, 1, 1, 0, 1, 0, 0, 0, 1, 0},
    {1, 1, 1, 0, 1, 0, 0, 0, 0, 0},
    {1, 1, 1, 0, 1, 0, 1, 1, 1, 1},
    {1, 1, 1, 1, 1, 0, 1, 1, 1, 1},
    {1, 1, 1, 1, 1, 0, 0, 0, 0, 1},
    {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
};
// 设置起终点，设起点(1,1)，终点(8,8)
int startX = 1, startY = 1;
int endX = 8, endY = 8;
// 定义方向数组：上、右、下、左的偏移量
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
// 栈存储路径节点，每个节点包含x、y坐标
struct Node {
    int x, y;
    Node(int x, int y) : x(x), y(y) {}
};
stack<Node> path;
// 打印迷宫状态
void printMigong() {
    for (int i = 0; i < hang; i++) {
        for (int j = 0; j < lie; j++) {
            if (migong[i][j] == 2) {
                cout << "* "; // 已走路径标记为*
            } else if (migong[i][j] == 3) {
                cout << "E "; // 终点标记为E
            } else if (migong[i][j] == 0) {
                cout << "0 "; // 可走路径
            } else {
                cout << "# "; // 墙壁
            }
        }
        cout << endl;
    }
    cout << "------------------------" << endl;
}

// 深度优先搜索求解迷宫
bool dfs(int x, int y) {
    // 到达终点，标记并返回成功
    if (x == endX && y == endY) {
        migong[x][y] = 3;
        path.push(Node(x, y));
        printMigong();
        return true;
    }
    // 标记当前节点为已走
    migong[x][y] = 2;
    path.push(Node(x, y));
    printMigong(); // 打印每一步状态
    // 尝试四个方向
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        // 检查新坐标是否在迷宫范围内，且可走（0或终点）
        if (nx >= 0 && nx < hang && ny >= 0 && ny < lie && (migong[nx][ny] == 0 || migong[nx][ny] == 3)) {
            if (dfs(nx, ny)) {
                return true; // 找到路径，回溯时直接返回
            }
        }
    }
    // 四个方向都走不通，回溯（弹出当前节点，标记为可走）
    path.pop();
    migong[x][y] = 0;
    printMigong(); // 打印回溯后的状态
    return false;
}

int main() {
    cout << "迷宫初始状态：" << endl;
    printMigong();

    cout << "开始寻找路径..." << endl;
    if (dfs(startX, startY)) {
        cout << "找到路径！路径如下：" << endl;
        stack<Node> reversePath;
        while (!path.empty()) {
            reversePath.push(path.top());
            path.pop();
        }
        while (!reversePath.empty()) {
            cout << "(" << reversePath.top().x << "," << reversePath.top().y << ") ";
            reversePath.pop();
        }
        cout << endl;
    } else {
        cout << "迷宫无解！" << endl;
    }

    return 0;
}


#include <iostream>
#include <stack>
#include <queue>
#include <iomanip>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <ctime>
using namespace std;

// 迷宫大小:10×10（核心区域）+2层围墙 = 12×12
const int hang = 12;
const int lie = 12;
const int MAX_STEP = 1000; // 最大探索步数

// 迷宫数组：1-不可走的墙壁，0-可走的路径，2-已走过的路径，3-终点
int migong[hang][lie];
// 探索标记（0:未探索，1:已探索，2:当前位置）
int visited[hang][lie];
// DFS路径记录
int path[MAX_STEP][2];
int path_len = 0;

// 设置起终点
int startX = 1, startY = 1;
int endX = 8, endY = 8;

// 定义方向数组：上、下、左、右的偏移量
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
char dir_name[4][3] = {"上", "下", "左", "右"};

// 节点结构（用于DFS）
struct Node {
    int x, y;
    Node(int x, int y) : x(x), y(y) {}
};
stack<Node> dfsPath;

// BFS相关（用于最短路径）
typedef struct {
    int x, y;       // 坐标
    int pre;        // 前驱索引
} BFSNode;
BFSNode bfs_queue[MAX_STEP];
int front = 0, rear = 0;
int bfs_visited[hang][lie] = {0};

// 打印迷宫状态（原DFS风格）
void printMigong() {
    for (int i = 1; i < hang - 1; i++) {  // 只打印核心10×10区域
        for (int j = 1; j < lie - 1; j++) {
            if (migong[i][j] == 2) {
                cout << "* "; // 已走路径标记为*
            } else if (migong[i][j] == 3) {
                cout << "E "; // 终点标记为E
            } else if (migong[i][j] == 0) {
                cout << "0 "; // 可走路径
            } else {
                cout << "# "; // 墙壁
            }
        }
        cout << endl;
    }
    cout << "------------------------" << endl;
}

// 打印探索步骤（BFS风格）
void print_step(int x, int y) {
    printf("\n===== 第%d步探索（位置：(%d,%d)）=====\n", path_len, x, y);
    for (int i = 1; i < hang - 1; i++) {
        for (int j = 1; j < lie - 1; j++) {
            if (migong[i][j] == 1) {
                printf("# ");          // 障碍
            } else if (i == x && j == y) {
                printf("@ ");          // 当前位置
            } else if (visited[i][j] == 1) {
                printf("* ");          // 已探索路径
            } else {
                printf("  ");          // 未探索通路
            }
        }
        printf("\n");
    }
}

// 初始化固定迷宫（基于原10×10迷宫扩展为12×12带围墙）
void init_fixed_maze() {
    // 外围围墙
    for (int i = 0; i < hang; i++) {
        migong[i][0] = migong[i][lie - 1] = 1;
        migong[0][i] = migong[hang - 1][i] = 1;
    }
    
    // 原10×10迷宫核心区域（复制到1-9行和1-9列）
    int core[10][10] = {
        {1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
        {1, 0, 1, 1, 0, 0, 0, 1, 1, 1},
        {1, 0, 0, 0, 0, 1, 0, 0, 0, 1},
        {1, 0, 0, 1, 1, 1, 1, 0, 1, 1},
        {1, 1, 1, 0, 1, 0, 0, 0, 1, 0},
        {1, 1, 1, 0, 1, 0, 0, 0, 0, 0},
        {1, 1, 1, 0, 1, 0, 1, 1, 1, 1},
        {1, 1, 1, 1, 1, 0, 1, 1, 1, 1},
        {1, 1, 1, 1, 1, 0, 0, 0, 0, 1},
        {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
    };
    
    // 复制核心区域到带围墙的迷宫
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10; j++) {
            migong[i][j] = core[i][j];
        }
    }
}

// 随机生成迷宫
void init_random_maze() {
    srand(time(0));
    // 初始化围墙
    for (int i = 0; i < hang; i++) {
        migong[i][0] = migong[i][lie - 1] = 1;
        migong[0][i] = migong[hang - 1][i] = 1;
    }
    // 随机生成内部（30%概率为障碍）
    for (int i = 1; i < hang - 1; i++) {
        for (int j = 1; j < lie - 1; j++) {
            migong[i][j] = (rand() % 10 < 3) ? 1 : 0;
        }
    }
    // 确保起点和终点为通路
    migong[startX][startY] = 0;
    migong[endX][endY] = 0;
}

// 深度优先搜索求解迷宫（保留原逻辑）
bool dfs(int x, int y) {
    // 到达终点，标记并返回成功
    if (x == endX && y == endY) {
        migong[x][y] = 3;
        dfsPath.push(Node(x, y));
        printMigong();
        return true;
    }
    // 标记当前节点为已走
    migong[x][y] = 2;
    dfsPath.push(Node(x, y));
    printMigong(); // 打印每一步状态
    
    // 尝试四个方向
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        // 检查新坐标是否在迷宫范围内，且可走（0或终点）
        if (nx >= 1 && nx < hang - 1 && ny >= 1 && ny < lie - 1 
            && (migong[nx][ny] == 0 || migong[nx][ny] == 3)) {
            if (dfs(nx, ny)) {
                return true; // 找到路径，回溯时直接返回
            }
        }
    }
    
    // 四个方向都走不通，回溯（弹出当前节点，标记为可走）
    dfsPath.pop();
    migong[x][y] = 0;
    printMigong(); // 打印回溯后的状态
    return false;
}

// BFS求解最短路径
void find_shortest_path() {
    // 初始化BFS队列
    front = rear = 0;
    memset(bfs_visited, 0, sizeof(bfs_visited));
    bfs_queue[rear++] = (BFSNode){startX, startY, -1};
    bfs_visited[startX][startY] = 1;
    int end_idx = -1;

    // BFS搜索
    while (front < rear) {
        BFSNode curr = bfs_queue[front++];
        if (curr.x == endX && curr.y == endY) {
            end_idx = front - 1;
            break;
        }
        // 探索四个方向
        for (int d = 0; d < 4; d++) {
            int nx = curr.x + dx[d];
            int ny = curr.y + dy[d];
            if (nx >= 1 && nx < hang - 1 && ny >= 1 && ny < lie - 1 
                && !bfs_visited[nx][ny] && migong[nx][ny] != 1) {
                bfs_visited[nx][ny] = 1;
                bfs_queue[rear++] = (BFSNode){nx, ny, front - 1};
            }
        }
    }

    // 回溯最短路径
    if (end_idx == -1) return;
    int shortest[hang * lie][2];
    int len = 0;
    int idx = end_idx;
    while (idx != -1) {
        shortest[len][0] = bfs_queue[idx].x;
        shortest[len][1] = bfs_queue[idx].y;
        len++;
        idx = bfs_queue[idx].pre;
    }

    // 打印最短路径
    printf("\n===== 最短路径结果 =====");
    printf("\n路径长度：%d步", len - 1);
    printf("\n路径（S→E）：");
    for (int i = len - 1; i >= 0; i--) {
        printf("(%d,%d)", shortest[i][0], shortest[i][1]);
        if (i > 0) printf("→");
    }

    // 打印带最短路径的迷宫
    printf("\n\n带最短路径的迷宫（*为最短路径）：\n");
    for (int i = 1; i < hang - 1; i++) {
        for (int j = 1; j < lie - 1; j++) {
            if (migong[i][j] == 1) {
                printf("# ");
            } else if (i == startX && j == startY) {
                printf("S ");  // 起点
            } else if (i == endX && j == endY) {
                printf("E ");  // 终点
            } else {
                bool is_shortest = false;
                for (int k = 0; k < len; k++) {
                    if (shortest[k][0] == i && shortest[k][1] == j) {
                        is_shortest = true;
                        break;
                    }
                }
                printf("%s ", is_shortest ? "*" : " ");
            }
        }
        printf("\n");
    }
}

int main() {
    int choice;
    
    // 保存原始迷宫用于后续BFS
    int originalMigong[hang][lie];
    
    // 选择迷宫类型
    printf("请选择迷宫类型：1-固定迷宫 2-随机生成迷宫：");
    scanf("%d", &choice);
    if (choice == 1) {
        init_fixed_maze();
    } else {
        init_random_maze();
    }
    
    // 保存原始迷宫
    memcpy(originalMigong, migong, sizeof(migong));
    
    // 自定义起点终点
    printf("使用默认起点终点？(1-是 2-自定义)：");
    scanf("%d", &choice);
    if (choice == 2) {
        printf("请输入起点坐标(x,y)（1≤x,y≤9）：");
        scanf("%d,%d", &startX, &startY);
        printf("请输入终点坐标(x,y)（1≤x,y≤9）：");
        scanf("%d,%d", &endX, &endY);
    } else {
        startX = 1; startY = 1;
        endX = 8; endY = 8;
    }
    
    // 检查起点终点合法性
    if (migong[startX][startY] == 1 || migong[endX][endY] == 1) {
        printf("起点或终点为障碍，无法探索！\n");
        return 0;
    }

    cout << "\n迷宫初始状态：" << endl;
    printMigong();

    cout << "开始寻找路径..." << endl;
    bool success = dfs(startX, startY);

    if (success) {
        cout << "找到路径！DFS路径如下：" << endl;
        stack<Node> reversePath;
        while (!dfsPath.empty()) {
            reversePath.push(dfsPath.top());
            dfsPath.pop();
        }
        while (!reversePath.empty()) {
            cout << "(" << reversePath.top().x << "," << reversePath.top().y << ") ";
            reversePath.pop();
        }
        cout << endl;
        
        // 恢复原始迷宫用于BFS
        memcpy(migong, originalMigong, sizeof(originalMigong));
        find_shortest_path();  // 求解并输出最短路径
    } else {
        cout << "迷宫无解！" << endl;
    }

    return 0;
}